package com.tucc.hello.leetcode.no1_400.no1_200.no61_80.no63;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] obstacleGrid = {
                {0, 1, 0},
                {0, 0, 0},
                {0, 0, 1}
        };
        System.out.println(solution.uniquePathsWithObstacles(obstacleGrid));
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return uniquePaths(obstacleGrid, obstacleGrid.length, obstacleGrid.length > 0 ?
                obstacleGrid[0].length : 0);
    }

    public int uniquePaths(int[][] obstacleGrid, int m, int n) {
        if (m > 0 && n > 0) {
            if(obstacleGrid[m - 1][n - 1] == 1){
                return 0;
            }
            int[][] dp = new int[m + 1][n + 1];
            dp[1][1] = 1 - obstacleGrid[0][0];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if(i == 1 && j == 1){
                        continue;
                    }
                    dp[i][j] = (j >= 2 ? (obstacleGrid[i - 1][j - 2] == 1 ? 0 : dp[i][j - 1]) : 0) +
                            (i >= 2 ? (obstacleGrid[i - 2][j - 1] == 1 ? 0 : dp[i - 1][j]) : 0);
                }
            }
            return dp[m][n];
        }
        return 0;
    }
}
